Mewarisi darah seni daripada ibunya yang merupakan seorang pereka dan pengusaha,[3] Avaa Vanja memulakan kerjayanya sebagai salah seorang ahli kumpulan Elite untuk tempoh jangka pendek,[4] iaitu selama 3 tahun, dari 2001 hingga 2004.[5][6] Kerjayanya sebagai pengacara bermula apabila beliau ditawarkan menjadi pengacara rancangan Pop TV terbitan KRU Studios.[7][8]

Kerjaya lakonan Avaa bermula apabila beliau berlakon dalam siri drama Sembilu (2003), yang diadaptasi dari filem 1994 bertajuk sama arahan Yusof Haslam. Beliau memegang watak sebagai Elisa. Beliau ditawarkan membintangi filem pertamanya,[9] Dukun (2006) arahan Dain Iskandar Said yang diharamkan tayangan selama 12 tahun. Avaa seterusnya membintangi filem hitam-putih Kala Malam Bulan Mengambang arahan Mamat Khalid yang mana beliau memegang watak sebagai Miss Rogayah.[10] Menerusi filem ini, beliau dicalonkan bagi kategori Pelakon Wanita Harapan di Festival Filem Malaysia ke-21.

Beliau membuat penampilan pentas pertamanya dengan membintangi Teater Muzikal Ibu Zain dengan melakonkan watak Miss Shellebear,[11] ini kemudian diikuti oleh teater Gamat. Kedua-dua teater ini dipentaskan di Istana Budaya.